// 扩展欧几里得、乘法逆元
// https://soj.turingedu.cn/problem/50507/

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) return x = 1, y = 0, a;
    ll ret = exgcd(b, a % b, y, x); // y = x1, x = y1
    y -= a / b * x;
    return ret;
}

ll inv(ll a, ll m) {
    ll g, x, y;
    g = exgcd(a, m, x, y);
    return g == 1 ? (x + m) % m : -1;
}
